//前K个高频单词
import java.util.*;

class Solution4 {
    public List<String> topKFrequent(String[] words, int k) {
        //1.先统计单词出现的次数->存储到map当中
        Map<String,Integer> map = new HashMap<>();
        for(String word : words){
            if(map.get(word) == null){
                map.put(word,1);
            }else{
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        //2.遍历统计好的Map 把每组数据存储到小根堆中
        PriorityQueue<Map.Entry<String,Integer>> minHeap=
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        //放元素的时候 如果频率相同 我们转变为大根堆-》按照单词的字典序
                        if(o1.getValue().compareTo(o2.getValue()) == 0) {
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
        for (Map.Entry<String,Integer> entry : map.entrySet()){
            if(minHeap.size() < k){
                minHeap.offer(entry);
            }else {
                //要找到最大评率的单词
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //def->2  abc->2
                    if (top.getValue().compareTo(entry.getValue()) == 0){
                        if (top.getKey().compareTo(entry.getKey()) > 0){
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        //放到小根堆 2 3 4
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        //2 3 4->4 3 2
        Collections.reverse(ret);
        return ret;
    }
}